101. 对称二叉树

#leetcode/tree/traversal

101. 对称二叉树

Similar Question

leading to the advanced question

Solution Tips

方案一: 递归

var isSymmetric = function(root) {
    // 可以理解成每一层节点都是回文的, 用层次遍历来做

    // 如果是用递归来做的话, 就是优先左遍历和优先右遍历结果是一样的
    // 但是这是对于整一个子树来说, 而不能递归到子树的子树上
    // 所以为了整体可以对比, 得在外面维护一个数组, 每 push 两个元素对比一次
    // 这种方案本质上还是迭代

    // 同时递归遍历两个节点的方法就是同时传入两个节点
    if (root === null) return null;

    return traversal(root.left, root.right)

    function traversal(n, m) {
        if (m.key !== m.key) return false;

        return traversal(n.left, m.right) && traversal(n.right, m.left);
    }
};

方案二: 迭代

const check = (u: TreeNode | null, v: TreeNode | null): boolean => {
    const q: (TreeNode | null)[] = [];
    q.push(u),q.push(v);

    while (q.length) {
        u = q.shift()!;
        v = q.shift()!;

        if (!u && !v) continue;
        if ((!u || !v) || (u.val !== v.val)) return false;

        q.push(u.left); 
        q.push(v.right);

        q.push(u.right); 
        q.push(v.left);
    }
    return true;
}
var isSymmetric = function(root: TreeNode | null): boolean {
    return check(root, root);
};